/**
 * 剑指 Offer 39. 数组中出现次数超过一半的数字
 */
class Solution {
    public int majorityElement(int[] nums) {
        int ret = nums[0];
        int count = 1;
        for (int i = 1;i<nums.length;i++){
            if (nums[i] == ret){
                count++;
            }else{
                count--;
            }
            if (count == 0){
                ret = nums[i];
                count = 1;
            }
        }
        return ret;
        
    }
}

/**
 * 剑指 Offer 50. 第一个只出现一次的字符
 */
class Solution2 {
    public char firstUniqChar(String s) {
        if (s.equals("")){
            return ' ';
        }
        char[] hash = new char[26];
        for (int i = 0;i<s.length();i++){
            char ch = s.charAt(i);
            hash[ch-'a']++;
        }
        for (int i = 0;i<s.length();i++){
            char ch = s.charAt(i);
            if (hash[ch-'a'] == 1){
                return ch;
            }
        }

        return ' ';
    }
}

/**
 * 剑指 Offer 53 - I. 在排序数组中查找数字 I
 */

class Solutio3 {
    public int search(int[] nums, int target) {
        int count = 0;
        for (int i = 0;i<nums.length;i++){
            if (target == nums[i]){
                count++;
            }
        }
        return count;
    }
}

/**
 * 第二种解法 二分 正解
 */
class Solution33 {
    public int search(int[] nums, int target) {
        int count = 0;
        int left = 0;
        int right = nums.length-1;
        while (left<right){//二分 找到第一个出现target数字下标
            int mid = (left+right)/2;
            if (nums[mid]>= target){//必须>= 才能满足循环结束条件
                right = mid;
            }else if (nums[mid]< target){
                left = mid+1;
            }
        }
        while (left <nums.length && nums[left++] == target){//从第一次出现的下标往后找
            count++;
        }
        return count;
    }
}